package com.ocean.sort;

import java.util.Arrays;

public class QuickSort2 {

    public static void main(String[] args) {
        QuickSort2 quickSort = new QuickSort2();
        int[] nums = {3, 1, 6, 2, 7, 9, 5, 4};
        quickSort.quickSort(nums, nums.length);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 使用分区得思想
     * <p>
     * 8 10 2 3 6 1 5
     *
     * @param nums
     * @param n
     */
    public void quickSort(int[] nums, int n) {
        quickSort(nums, 0, n - 1);
    }

    private void quickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int q = partition(nums, start, end);
        quickSort(nums, start, q - 1);
        quickSort(nums, q + 1, end);
    }

    private int partition(int[] nums, int start, int end) {
        int item = nums[end];
        int i = start;
        for (int j = start; j <= end - 1; j++) {
            if (nums[j] < item) {
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
                i++;
            }
        }
        nums[end] = nums[i];
        nums[i] = item;
        return i;
    }
}
